package ru.algorithm.clusterization.cftree2;

/**
 * Yuri Zemlyanskiy <urikz@yandex-team.ru>
 * Date: 05.05.2011
 */
public class CFTree {
//    private long step = 0;
//    private long memoryLimit = (long) Math.pow(1024, 3); // default = 1GB
//    private long periodicMemLimitCheck = 100000;
//
//    private AbstractCFInnerNode root;
//    private int brachingLevel;
//    private double distTreshold;
//
//    public CFTree(int brachingLevel, double distThreshold) {
//        this.brachingLevel = brachingLevel;
//        this.distTreshold = distThreshold;
//
////        this.root = new AbstractCFInnerNode(brachingLevel);
//    }
//
//    public long getMemoryLimit() {
//        return memoryLimit;
//    }
//
//    /**
//     * Inserts a single pattern vector into the CFTree
//     * @param point the pattern vector to be inserted in the tree
//     */
//    public void insert(double[] point) {
//        final CFLeaf leaf = new CFLeaf(point);
//        boolean shouldNotSplit = root.insert(leaf);
//        step++;
//        if (!shouldNotSplit) {
//            splitRoot();
//            rebuildIfAboveMemLimit();
//        } else {
//            if ((step % periodicMemLimitCheck) == 0) {
//                rebuildIfAboveMemLimit();
//            }
//        }
//    }
//
//    // TODO : fix me
//    private boolean rebuildIfAboveMemLimit() {
//        if (hasReachedMemoryLimit(this, memoryLimit)) {
////            double newThreshold = computeNewThreshold(leafListStart, root.getDistFunction(), root.getDistThreshold());
////            CFTree newTree = this.rebuildTree(root.getMaxNodeEntries(), newThreshold, root.getDistFunction(), root.applyMergingRefinement(), false);
////            copyTree(newTree);
//            return true;
//        }
//        return false;
//    }
//
//    private void splitRoot() {
//        // the split happens by finding the two entries in this node that are the most far apart
//        // we then use these two entries as a "pivot" to redistribute the old entries into two new nodes
//
//        CFEntryPair p = root.findFarthestEntryPair(root.getEntries());
//
//        CFEntry newEntry1 = new CFEntry();
//        CFNode newNode1 = new CFNode(root.getMaxNodeEntries(), root.getDistThreshold(), root.getDistFunction(), root.applyMergingRefinement(), root.isLeaf());
//        newEntry1.setChild(newNode1);
//
//        CFEntry newEntry2 = new CFEntry();
//        CFNode newNode2 = new CFNode(root.getMaxNodeEntries(), root.getDistThreshold(), root.getDistFunction(), root.applyMergingRefinement(), root.isLeaf());
//        newEntry2.setChild(newNode2);
//
//        // the new root that hosts the new entries
//        CFNode newRoot = new CFNode(root.getMaxNodeEntries(), root.getDistThreshold(), root.getDistFunction(), root.applyMergingRefinement(), false);
//        newRoot.addToEntryList(newEntry1);
//        newRoot.addToEntryList(newEntry2);
//
//        // this updates the pointers to the list of leaves
//        if (root.isLeaf()) { // if root was a leaf
//            leafListStart.setNextLeaf(newNode1);
//            newNode1.setPreviousLeaf(leafListStart);
//            newNode1.setNextLeaf(newNode2);
//            newNode2.setPreviousLeaf(newNode1);
//        }
//
//        // redistributes the entries in the root between newEntry1 and newEntry2
//        // according to the distance to p.e1 and p.e2
//        root.redistributeEntries(root.getEntries(), p, newEntry1, newEntry2);
//
//        // updates the root
//        root = newRoot;
//
//        // frees some memory by deleting the nodes in the tree that had to be split
//        System.gc();
//
//    }
//
//    /**
//     * Overwrites the structure of this tree (all nodes, entreis, and leaf list) with the structure of newTree.
//     *
//     * @param newTree the tree to be copied
//     */
//    private void copyTree(CFTree newTree) {
//        this.root = newTree.root;
//        this.leafListStart = newTree.leafListStart;
//    }
//
//    /**
//     * Computes a new threshold based on the average distance of the closest subclusters in each leaf node
//     *
//     * @param leafListStart    the pointer to the start of the list (the first node is assumed to be a place-holder dummy node)
//     * @param distFunction
//     * @param currentThreshold
//     * @return the new threshold
//     */
//    public double computeNewThreshold(CFNode leafListStart, int distFunction, double currentThreshold) {
//        double avgDist = 0;
//        int n = 0;
//
//        CFNode l = leafListStart.getNextLeaf();
//        while (l != null) {
//            if (!l.isDummy()) {
//                CFEntryPair p = l.findClosestEntryPair(l.getEntries());
//                if (p != null) {
//                    avgDist += p.e1.distance(p.e2, distFunction);
//                    n++;
//
//                    /* This is a possible alternative: Overall avg distance between leaf entries
//                    CFEntry[] v = l.getEntries().toArray(new CFEntry[0]);
//                    for(int i=0; i < v.length-1; i++) {
//                        for(int j=i+1; j < v.length; j++) {
//                            avgDist += v[i].distance(v[j], distFunction);
//                            n++;
//                        }
//                    }*/
//                }
//            }
//            l = l.getNextLeaf();
//        }
//
//        double newThreshold = 0;
//        if (n > 0)
//            newThreshold = avgDist / n;
//
//        if (newThreshold <= currentThreshold) { // this guarantees that newThreshold always increases compared to currentThreshold
//            newThreshold = 2 * currentThreshold;
//        }
//
//        return newThreshold;
//    }
//
//    private boolean hasReachedMemoryLimit(CFTree tree, long limit) {
//        long memory = computeMemorySize(tree);
//        return memory >= limit;
//    }
//
//    private long computeMemorySize(CFTree t) {
//        long memSize = 0;
//        try {
//            memSize = SizeOf.iterativeSizeOf(t);
//        }
//        catch (Exception e) {
//            System.err.println("#################### ERROR WHEN COMPUTING MEMORY SIZE: " + e);
//        }
//        return memSize;
//    }
//
//    /**
//     * This implementation of the rebuilding algorithm is different from
//     * the one described in Section 4.5 of the paper. However the effect
//     * is practically the same. Namely, given a tree t_i build using
//     * threshold T_i, if we set a new threshold T_(i+1) and call
//     * rebuildTree (assuming maxEntries stays the same) we will obtain
//     * a more compact tree.
//     * <p/>
//     * Since the CFTree is sensitive to the order of the data, there
//     * may be cases in which, if we set the T_(i+1) so that non of the
//     * sub-clusters (i.e., the leaf entries) can be merged (e.g., T_(i+1)=-1)
//     * we might actually obtain a new tree t_(i+1) containing more nodes
//     * than t_i. However, the obtained sub-clusters in t_(i+1) will be
//     * identical to the sub-clusters in t_i.
//     * <p/>
//     * In practice, though, if T_(i+1) > T_(i), the tree t_(i+1) will
//     * usually be smaller than t_i.
//     * Although the Reducibility Theorem in Section 4.5 may not hold
//     * anymore, in practice this will not be a big problem, since
//     * even in those cases in which t_(i+1)>t_i, the growth should
//     * be very small.
//     * <p/>
//     * The advantage is that relaxing the constraint that the size
//     * of t_(i+1) must be less than t_i makes the implementation
//     * of the rebuilding algorithm much easier.
//     *
//     * @param newMaxEntries          the new number of entries per node
//     * @param newThreshold           the new threshold
//     * @param applyMergingRefinement if true, merging refinement will be applied after every split
//     * @param discardOldTree         if true, the old tree will be discarded (to free memory)
//     * @return the new (usually more compact) CFTree
//     */
//    public CFTree rebuildTree(int newMaxEntries, double newThreshold, int distFunction, boolean applyMergingRefinement, boolean discardOldTree) {
//        CFTree newTree = new CFTree(newMaxEntries, newThreshold, distFunction, applyMergingRefinement);
//        newTree.instanceIndex = this.instanceIndex;
//        newTree.memoryLimit = this.memoryLimit;
//
//        CFNode oldLeavesList = this.leafListStart.getNextLeaf(); // remember: the node this.leafListStart is a dummy node (place holder for beginning of leaf list)
//
//        if (discardOldTree) {
//            this.root = null;
//            System.gc(); // removes the old tree. Only the old leaves will be kept
//        }
//
//        CFNode leaf = oldLeavesList;
//        while (leaf != null) {
//            if (!leaf.isDummy()) {
//                for (CFEntry e : leaf.getEntries()) {
//                    CFEntry newE = e;
//                    if (!discardOldTree) // we need to make a deep copy of e
//                        newE = new CFEntry(e);
//
//                    newTree.insertEntry(newE);
//                }
//            }
//
//            leaf = leaf.getNextLeaf();
//        }
//
//        if (discardOldTree) {
//            this.leafListStart = null;
//            System.gc(); // removes the old list of leaves
//        }
//
//        return newTree;
//    }
//
//
//    /**
//     * @return a list of subcluster, and for each subcluster a list of pattern vector indexes that belong to it
//     */
//    public ArrayList<ArrayList<Integer>> getSubclusterMembers() {
//        ArrayList<ArrayList<Integer>> membersList = new ArrayList<ArrayList<Integer>>();
//
//        CFNode l = leafListStart.getNextLeaf(); // the first leaf is dummy!
//        while (l != null) {
//            if (!l.isDummy()) {
//                // System.out.println(l);
//                for (CFEntry e : l.getEntries())
//                    membersList.add(e.getIndexList());
//            }
//            l = l.getNextLeaf();
//        }
//
//        return membersList;
//    }
//
//    /**
//     * Signals the fact that we finished inserting data.
//     * The obtained subclusters will be assigned a positive, unique ID number
//     */
//    public void finishedInsertingData() {
//        CFNode l = leafListStart.getNextLeaf(); // the first leaf is dummy!
//
//        int id = 0;
//        while (l != null) {
//            if (!l.isDummy()) {
//                // System.out.println(l);
//                for (CFEntry e : l.getEntries()) {
//                    id++;
//                    e.setSubclusterID(id);
//                }
//            }
//            l = l.getNextLeaf();
//        }
//    }
//
//    /**
//     * Retrieves the subcluster id of the closest leaf entry to e
//     *
//     * @param e the entry to be mapped
//     * @return a positive integer, if the leaf entries were enumerated using finishedInsertingData(), otherwise -1
//     */
//    public int mapToClosestSubcluster(double[] x) {
//        CFEntry e = new CFEntry(x);
//
//        return root.mapToClosestSubcluster(e);
//
//    }
//
//    /**
//     * Computes an estimate of the cost of running an O(n^2) algorithm to split each subcluster in more fine-grained clusters
//     *
//     * @return sqrt(sum_i[(n_i)^2]), where n_i is the number of members of the i-th subcluster
//     */
//    public double computeSumLambdaSquared() {
//        double lambdaSS = 0;
//
//        CFNode l = leafListStart.getNextLeaf();
//        while (l != null) {
//            if (!l.isDummy()) {
//                for (CFEntry e : l.getEntries()) {
//                    lambdaSS += Math.pow(e.getIndexList().size(), 2);
//                }
//            }
//            l = l.getNextLeaf();
//        }
//
//        return Math.sqrt(lambdaSS);
//    }
//
//    /**
//     * prints the CFTree
//     */
//    public void printCFTree() {
//        System.out.println(root);
//    }
//
//    /**
//     * Counts the nodes of the tree (including leaves)
//     *
//     * @return the number of nodes in the tree
//     */
//    public int countNodes() {
//        int n = 1; // at least root has to be present
//        n += root.countChildrenNodes();
//
//        return n;
//    }
//
//    /**
//     * Counts the number of CFEntries in the tree
//     *
//     * @return the number of entries in the tree
//     */
//    public int countEntries() {
//        int n = root.size(); // at least root has to be present
//        n += root.countEntriesInChildrenNodes();
//
//        return n;
//    }
//
//    /**
//     * Counts the number of leaf entries (i.e., the number of sub-clusters in the tree)
//     *
//     * @return the number of leaf entries (i.e., the number of sub-clusters)
//     */
//    public int countLeafEntries() {
//        int i = 0;
//        CFNode l = leafListStart.getNextLeaf();
//        while (l != null) {
//            if (!l.isDummy()) {
//                i += l.size();
//            }
//
//            l = l.getNextLeaf();
//        }
//
//        return i;
//    }
//
//    /**
//     * Prints the index of all the pattern vectors that fall into the leaf nodes.
//     * This is only useful for debugging purposes.
//     */
//    public void printLeafIndexes() {
//        ArrayList<Integer> indexes = new ArrayList<Integer>();
//
//        CFNode l = leafListStart.getNextLeaf();
//        while (l != null) {
//            if (!l.isDummy()) {
//                System.out.println(l);
//                for (CFEntry e : l.getEntries())
//                    indexes.addAll(e.getIndexList());
//            }
//            l = l.getNextLeaf();
//        }
//
//        Integer[] v = indexes.toArray(new Integer[0]);
//        Arrays.sort(v);
//        System.out.println("Num of Indexes = " + v.length);
//        System.out.println(Arrays.toString(v));
//    }
//
//    /**
//     * Prints the index of the pattern vectors in each leaf entry (i.e., each subcluster)
//     */
//    public void printLeafEntries() {
//        int i = 0;
//        CFNode l = leafListStart.getNextLeaf();
//        while (l != null) {
//            if (!l.isDummy()) {
//                for (CFEntry e : l.getEntries()) {
//                    System.out.println("[[" + (++i) + "]]");
//                    Integer[] v = e.getIndexList().toArray(new Integer[0]);
//                    Arrays.sort(v);
//                    System.out.println(Arrays.toString(v));
//                }
//            }
//
//            l = l.getNextLeaf();
//        }
//    }
//

}
